home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1996 May: Tool Chest / Developer CD Series May 1996 (Tool Chest) (Apple Computer) (1996).iso / Tool Chest / Development Tools & Languages / Dylan Related / Mindy / Mindy 1.2 - portable sources / interp / gc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-03-15  |  9.0 KB  |  364 lines  |  [TEXT/ttxt]
  1. /**********************************************************************\
  2. *
  3. *  Copyright (c) 1994  Carnegie Mellon University
  4. *  All rights reserved.
  5. *  
  6. *  Use and copying of this software and preparation of derivative
  7. *  works based on this software are permitted, including commercial
  8. *  use, provided that the following conditions are observed:
  9. *  
  10. *  1. This copyright notice must be retained in full on any copies
  11. *     and on appropriate parts of any derivative works.
  12. *  2. Documentation (paper or online) accompanying any system that
  13. *     incorporates this software, or any part of it, must acknowledge
  14. *     the contribution of the Gwydion Project at Carnegie Mellon
  15. *     University.
  16. *  
  17. *  This software is made available "as is".  Neither the authors nor
  18. *  Carnegie Mellon University make any warranty about the software,
  19. *  its performance, or its conformity to any specification.
  20. *  
  21. *  Bug reports, questions, comments, and suggestions should be sent by
  22. *  E-mail to the Internet address "gwydion-bugs@cs.cmu.edu".
  23. *
  24. ***********************************************************************
  25. *
  26. * $Header: gc.c,v 1.18 94/12/07 18:48:37 wlott Exp $
  27. *
  28. * This file is the garbage collector.
  29. *
  30. \**********************************************************************/
  31.  
  32. #include "../compat/std-c.h"
  33.  
  34. #include "mindy.h"
  35. #include "class.h"
  36. #include "gc.h"
  37. #include "weak.h"
  38. #include "table.h"
  39.  
  40. extern void scavenge_thread_roots(void);
  41. extern void scavenge_bool_roots(void);
  42. extern void scavenge_class_roots(void);
  43. extern void scavenge_coll_roots(void);
  44. extern void scavenge_func_roots(void);
  45. extern void scavenge_instance_roots(void);
  46. extern void scavenge_interp_roots(void);
  47. extern void scavenge_list_roots(void);
  48. extern void scavenge_num_roots(void);
  49. extern void scavenge_obj_roots(void);
  50. extern void scavenge_vec_roots(void);
  51. extern void scavenge_str_roots(void);
  52. extern void scavenge_char_roots(void);
  53. extern void scavenge_symbol_roots(void);
  54. extern void scavenge_type_roots(void);
  55. extern void scavenge_module_roots(void);
  56. extern void scavenge_value_roots(void);
  57. extern void scavenge_debug_roots(void);
  58. extern void scavenge_handler_roots(void);
  59. extern void scavenge_load_roots(void);
  60. extern void scavenge_nlx_roots(void);
  61. extern void scavenge_driver_roots(void);
  62. extern void scavenge_buffer_roots(void);
  63. extern void scavenge_weak_roots(void);
  64. extern void scavenge_brkpt_roots(void);
  65. extern void scavenge_table_roots(void);
  66. extern void scavenge_c_roots(void);
  67.  
  68. #define CHECKGC 0
  69.  
  70. boolean TimeToGC = FALSE;
  71.  
  72. struct block {
  73.     struct block *next;
  74.     void *base;
  75.     void *end;
  76.     void *fill;
  77. };
  78.  
  79. #define BLOCK_SIZE (128*1024)
  80. #define BYTES_CONSED_BETWEEN_GCS (2*1024*1024)
  81.  
  82. static struct block *FreeBlocks = 0;
  83. static struct block *UsedBlocks = 0;
  84. #if CHECKGC
  85. static struct block *OldBlocks = 0;
  86. #endif
  87. static struct block *cur_block = 0;
  88. static void *cur_fill = 0, *cur_end = 0;
  89. static int BytesInUse = 0;
  90. static int GCTrigger = BYTES_CONSED_BETWEEN_GCS;
  91.  
  92. static int bytes_in_use(void)
  93. {
  94.     if (cur_block)
  95.     return BytesInUse + ((char *)cur_fill - (char *)cur_block->base);
  96.     else
  97.     return BytesInUse;
  98. }
  99.  
  100. void *raw_alloc(int bytes)
  101. {
  102.     void *result;
  103.  
  104.     if (bytes < 0)
  105.     lose("Can't allocate a negative number of bytes: %d", bytes);
  106.  
  107.     /* round bytes up to the next dual-word boundy. */
  108.     bytes = (bytes + 7) & ~7;
  109.  
  110.     if (bytes > BLOCK_SIZE - sizeof(struct block))
  111.     lose("Can't allocate %d bytes, %d at most.",
  112.          bytes, BLOCK_SIZE - sizeof(struct block));
  113.  
  114.     if ((char *)cur_fill + bytes > (char *)cur_end) {
  115.     struct block *block;
  116.  
  117.     if (FreeBlocks) {
  118.         block = FreeBlocks;
  119.         FreeBlocks = block->next;
  120.     }
  121.     else {
  122.         block = malloc(BLOCK_SIZE);
  123.         block->base = (char *)block + sizeof(struct block);
  124.         block->end = (char *)block + BLOCK_SIZE;
  125.     }
  126.     block->next = 0;
  127.  
  128.     if (cur_block) {
  129.         BytesInUse += (char *)cur_fill - (char *)cur_block->base;
  130.         cur_block->fill = cur_fill;
  131.         cur_block->next = block;
  132.         if (BytesInUse > GCTrigger)
  133.         TimeToGC = TRUE;
  134.     }
  135.     else
  136.         UsedBlocks = block;
  137.  
  138.     cur_block = block;
  139.     cur_fill = block->base;
  140.     cur_end = block->end;
  141.     }
  142.  
  143.     result = cur_fill;
  144.     cur_fill = (char *)cur_fill + bytes;
  145.  
  146.     return result;
  147. }
  148.  
  149. obj_t alloc(obj_t class, int bytes)
  150. {
  151. #if CHECKGC
  152.     unsigned int *ptr;
  153. #else
  154.     void *ptr;
  155. #endif
  156.     obj_t result;
  157.  
  158.     if (class == NULL)
  159.     lose("Tried to allocate a class that hasn't been created yet.");
  160.  
  161. #if CHECKGC
  162.     if (class != ptr_obj(NULL)
  163.       && *obj_ptr(int *, class) == 0xfacefeed)
  164.     lose("Tried to allocate a class that wasn't scavenged.");
  165.  
  166.     ptr = raw_alloc(bytes + sizeof(int)*2);
  167.     ptr[0] = 0xbeadbabe;
  168.     ptr[1] = bytes;
  169.  
  170.     result = ptr_obj(ptr + 2);
  171. #else
  172.     ptr = raw_alloc(bytes);
  173.     result = ptr_obj(ptr);
  174. #endif
  175.  
  176.     obj_ptr(struct object *, result)->class = class;
  177.  
  178.     return result;
  179. }
  180.  
  181. void shrink(obj_t obj, int new_bytes)
  182. {
  183. #if CHECKGC
  184.     unsigned int *ptr = obj_ptr(unsigned int *, obj) - 2;
  185.  
  186.     if (new_bytes > ptr[1])
  187.     lose("Can't shrink a %d byte object to %d bytes.", ptr[1], new_bytes);
  188.  
  189.     ptr[1] = new_bytes;
  190. #endif    
  191. }
  192.  
  193. struct forwarding_pointer {
  194.     obj_t marker;
  195.     obj_t new_value;
  196. };
  197.  
  198. void scavenge(obj_t *addr)
  199. {
  200.     obj_t obj = *addr;
  201.  
  202.     if (obj_is_ptr(obj)) {
  203.     obj_t class = obj_ptr(struct object *, obj)->class;
  204.     if (class == ForwardingMarker)
  205.         *addr = obj_ptr(struct forwarding_pointer *, obj)->new_value;
  206.     else
  207.         *addr = obj_ptr(struct class *, class)->transport(obj);
  208.     }
  209. }
  210.  
  211. obj_t transport(obj_t obj, int bytes)
  212. {
  213. #if CHECKGC
  214.     unsigned int *new;
  215.     unsigned int *ptr = obj_ptr(unsigned int *, obj) - 2;
  216. #else
  217.     void *new;
  218. #endif
  219.     obj_t new_obj;
  220.  
  221. #if CHECKGC
  222.     if (ptr[0] != 0xbeadbabe)
  223.     lose("Someone called transport with a bogus object.");
  224.     if (ptr[1] != bytes)
  225.     lose("Someone told transport that %d byte object was %d bytes.",
  226.          ptr[1], bytes);
  227.  
  228.     new = raw_alloc(bytes + sizeof(int)*2);
  229.     new_obj = ptr_obj(new + 2);
  230.  
  231.     memcpy(new, ptr, bytes + sizeof(int)*2);
  232. #else
  233.     new = raw_alloc(bytes);
  234.     new_obj = ptr_obj(new);
  235.     memcpy(new, obj_ptr(void *, obj), bytes);
  236. #endif
  237.  
  238.     obj_ptr(struct forwarding_pointer *, obj)->marker = ForwardingMarker;
  239.     obj_ptr(struct forwarding_pointer *, obj)->new_value = new_obj;
  240.  
  241.     return new_obj;
  242. }
  243.  
  244. static void scavenge_newspace(void)
  245. {
  246.     struct block *block = UsedBlocks;
  247.     void *ptr, *end;
  248.     obj_t class;
  249.     int bytes;
  250.  
  251.     while (block != 0) {
  252.     ptr = block->base;
  253.     /* The reason for this double loop is so that we don't have to */
  254.     /* do the block->next conditional each time around the inner loop. */
  255.     while (ptr < (end = (block->next ? block->fill : cur_fill))) {
  256.         do {
  257. #if CHECKGC
  258.         unsigned int *header = ptr;
  259.         if (header[0] != 0xbeadbabe)
  260.             lose("Scavenge_newspace found a bogus object.");
  261.         ptr = (char *)ptr + sizeof(int)*2;
  262. #endif
  263.         scavenge((obj_t *)ptr);
  264.         class = *(obj_t *)ptr;
  265.         bytes = obj_ptr(struct class *, class)->scavenge(ptr);
  266. #if CHECKGC
  267.         if (header[1] != bytes)
  268.             lose("Some scavenger claimed a %d byte object "
  269.              "was %d bytes.",
  270.              header[1], bytes);
  271. #endif
  272.         ptr = (char *)ptr + ((bytes + 7) & ~7);
  273.         } while (ptr < end);
  274.     }
  275.     block = block->next;
  276.     }
  277. }
  278.  
  279. void collect_garbage(void)
  280. {
  281.     struct block *old_blocks = UsedBlocks;
  282.     int bytes_at_start = bytes_in_use();
  283.     int bytes_at_end;
  284.  
  285.     fprintf(stderr, "[GCing with %d bytes in use...", bytes_at_start);
  286.     fflush(stderr);
  287.  
  288.     BytesInUse = 0;
  289.     UsedBlocks = 0;
  290.     cur_block = 0;
  291.     cur_fill = 0;
  292.     cur_end = 0;
  293.  
  294.     scavenge_thread_roots();
  295.     scavenge_bool_roots();
  296.     scavenge_class_roots();
  297.     scavenge_coll_roots();
  298.     scavenge_func_roots();
  299.     scavenge_instance_roots();
  300.     scavenge_interp_roots();
  301.     scavenge_list_roots();
  302.     scavenge_num_roots();
  303.     scavenge_obj_roots();
  304.     scavenge_vec_roots();
  305.     scavenge_str_roots();
  306.     scavenge_char_roots();
  307.     scavenge_symbol_roots();
  308.     scavenge_type_roots();
  309.     scavenge_module_roots();
  310.     scavenge_value_roots();
  311.     scavenge_debug_roots();
  312.     scavenge_handler_roots();
  313.     scavenge_load_roots();
  314.     scavenge_nlx_roots();
  315.     scavenge_driver_roots();
  316.     scavenge_buffer_roots();
  317.     scavenge_weak_roots();
  318.     scavenge_brkpt_roots();
  319.     scavenge_table_roots();
  320.     scavenge_c_roots();
  321.  
  322.     scavenge_newspace();
  323.  
  324.     break_weak_pointers();
  325.  
  326. #if CHECKGC
  327.     {
  328.     struct block *block, *next;
  329.     for (block = OldBlocks; block != NULL; block = next) {
  330.         next = block->next;
  331.         block->next = FreeBlocks;
  332.         FreeBlocks = block;
  333.     }
  334.     OldBlocks = NULL;
  335.     for (block = old_blocks; block != NULL; block = next) {
  336.         unsigned int *ptr;
  337.         next = block->next;
  338.         block->next = OldBlocks;
  339.         OldBlocks = block;
  340.         for (ptr = block->base; ptr < (unsigned int *)block->end; ptr++)
  341.         *ptr = 0xfacefeed;
  342.     }
  343.     }
  344. #else
  345.     while (old_blocks != 0) {
  346.     struct block *next = old_blocks->next;
  347.     old_blocks->next = FreeBlocks;
  348.     FreeBlocks = old_blocks;
  349.     old_blocks = next;
  350.     }
  351. #endif
  352.  
  353.     bytes_at_end = bytes_in_use();
  354.     GCTrigger = bytes_at_end + BYTES_CONSED_BETWEEN_GCS;
  355.     TimeToGC = FALSE;
  356.  
  357.     fprintf(stderr, "reclaimed %d leaving %d]\n",
  358.         bytes_at_start - bytes_at_end,
  359.         bytes_at_end);
  360.     fflush(stderr);
  361.  
  362.     table_gc_hook();
  363. }
  364.